1. Field of the Invention
The present invention relates to a content addressable memory (CAM)(which is also generally called an xe2x80x9cassociative memoryxe2x80x9d)
2. Description of the Related Art
Conventionally, a content addressable memory (CAM) is known as a memory used such that storage data is stored in each of a plurality of word memories (which constitute a memory region) to permit overwriting, retrieval data is entered, and storage data corresponding to the retrieval data is retrieved.
One of the major applications is a network frame repeater that relays communications of network frames. The network frame repeater will be outlined hereinbelow.
Conventionally, a network system includes a network frame repeater called, for example, a xe2x80x9chubxe2x80x9d. The network frame repeater relays transmission of network frames, each of which is a packet of information that is communicated in the network system.
FIG. 3 is a circuit block diagram showing an example configuration of a network frame repeater 30.
The network frame repeater 30 includes n pieces of port controllers 32_1 to 32_n connected to a bus 31. In addition, a plurality of terminals A, B, . . . , C and a plurality of terminals E, F, . . . , G are connected via local area networks 34_1 to 34_n (LANs) to ports 33_1 to 33_n, respectively, which correspond to the port controllers 32_1 to 32_n.
In addition, the bus 31 is connected to a CAM 35, a random access memory 36 (RAM), a central processing unit 37 (CPU), and a packet memory 38.
Compared to an ordinary RAM, the CAM 35, to which a retrieval function is added, is expensive in terms of the cost per bit and has a small memory capacity. To solve this problem, the network frame repeater 30 shown in FIG. 3 uses both the CAM 35 and the RAM 36. Data directly required for retrieval is stored in the CAM 35, and data not directly required for retrieval is stored in the RAM 36. The addresses of word memories of the CAM 35 are correlated to the addresses of memory regions of the RAM 36 via a signal line 39. The CAM 35 stores address data representing the addresses of the individual terminals and time stamp data (which will be described hereafter). On the other hand, the RAM 36 stores the port numbers of the individual ports 33_1 to 33_n connected to the terminals. In addition, the RAM 36 stores other data, such as data related to a virtual LAN (VLAN), and data accessed by hardware of the network frame repeater 30 (detailed description of the data is omitted herefrom).
The CPU 37 performs the overall control of the network frame repeater 30. The packet memory 38 temporarily stores received network frames.
Ordinarily, the network frame repeater 30 includes various other devices. However, since the devices are not directly concerned with the intended subject matter, they are neither described nor illustrated.
Hereinbelow, description will be made with reference to an example case where information in the form of a network frames is transmitted from the terminal B connected to the LAN 34_1 to the terminal E connected to the LAN 34_n.
A header portion of the network frame contains data identifying a destination address representing the terminal E, and a transmission source address representing the terminal B.
The network frame transmitted from terminal B via the port 33_1 is controlled to pass through the port controller 32_1 and the bus 31, and is then temporarily stored in the packet memory 38. The CPU 37 extracts the destination address representing a data transmission destination (terminal E in the example case) from the header portion of the network frame, and then sends it to the CAM 35. The CAM 35 contains address data representing the individual terminals A, B, . . . , C and the individual terminals E, F, . . . , G, which constitute the network system. On the other hand, the RAM 36 stores the port numbers individually identifying destinations to which the terminals A, B, . . . , C and the terminals E, F, . . . , G are connected via the ports 33_1 to 33_n. Address data representing the destination address is input into the CAM 35. Subsequently, the CAM 35 outputs to the signal line 39 an HHA (highest hit address) of a word memory of the CAM 35, which contains address data identical to the aforementioned input address data. In response to the output, the port number representing the destination terminal indicated by the destination address is read out of the address corresponding to the HHA of the RAM 36. Based on the port number that has been read out, the CPU 37 recognizes the present network frame as data that is due to be transmitted to port 33_n.
When the port number is read out of the RAM 36 in the above-described manner, the network frame is input from the packet memory 38 via the bus 31 to the port controller 32_n, and is further sent to the terminal E via the port 33_n and the LAN 34_n.
In this way, the network frame repeater 30 uses CAM 35 for performing high-speed retrieval of addresses.
FIG. 4 shows a MAC (media access control) table in the network frame repeater 30 shown in FIG. 3.
The MAC table shown in FIG. 4 contains address data representing the addresses (MAC addresses) of the terminals A, B, . . . , C and terminals E, F, . . . , G; the corresponding port numbers; and the corresponding time stamp data.
As described above, a destination address extracted from a network frame is used for retrieval. The port number to which the network frame is to be transmitted can be known from a retrieved address stored in the RAM 36, which corresponds to the HHA. As shown in FIG. 4, in addition to terminal address data, each of the word memories also contains time stamp data. Hereinbelow, the time stamp data will be described.
FIG. 5 is a view for explaining time stamp data.
As shown in FIG. 5, a predetermined time interval is set for one time slot, and p pieces of the time slots are cycled one by one as time passes. To discriminate the p pieces of the time slots from each other, their numbers, for example, numerals 1, 2, . . . , and p are assigned to represent the time stamp data T1, T2, . . . , and Tp, respectively.
In the CAM 35, in an event where a retrieval has been carried out by using a source address extracted from a network frame, the retrieval has detected an address identical to the source address thereof, time stamp data of the corresponding word memory is overwritten with the time stamp data that represents the time slot at that time (current time). However, in an event where the retrieval has not detected an address identical to the source address, data of the source address and time stamp data representing a time slot of the current time is written into a empty address field (empty word memory). On the other hand, into the RAM 36 are written the port number of a port from which a network frame having that source address has been transmitted. In the CAM 35, at each time interval that defines each of the time slots, retrieval is carried out by using the time stamp data of the time slot (time slot whereat the longest time has passed) immediately preceding the current time slot. As a result, if time stamp data identical to the input time stamp data is detected, data in the corresponding word memory is erased. By erasing the address data of terminals that have not been involved in communication for a long time, a empty address field is secured in the CAM 35, thereby enabling the CAM 35 to store new data. In this case, the erasure of data means that, for example, one bit in the word memory is allocated as a bit (empty bit) that is used to determine the existence of data, and the bit is overwritten so as to be converted from logic representing a data-existence to logic representing a data-nonexistence. In addition, each of the word memories may have an empty flag as a flipflop that indicates whether valid data is stored or not in the word memory, and data can be erased by overwriting the flag.
In this way, in the CAM 35, retrieval is performed for a time stamp data that the longest time has passed after set, and data regarding a terminal that has not been involved in communication is thereby erased. However, in a configuration where, for example, a server is connected as a terminal to the network frame repeater 30, a request is usually made for not erasing data regarding the server even when the server is not involved in communication for a long time. To comply with the request, a technique has been proposed. According to the proposed technique, the permanent bit corresponding to the address data of each terminal is registered in a MAC table as shown in FIG. 4, in which, when a permanent bit corresponding to data which should not be erased is set, the address data is not erased. However, the technique requires the permanent bit to be provided for each piece of terminal address data, thereby requiring an increased memory bit capacity.
According to another proposed technique, data which should not be erased among data registered in a MAC table is preliminarily saved, and the saved data is returned to the MAC table after retrieval. In this technique, however, every time a retrieval is performed by using time stamp data, read and write operations need to be performed with address data which should not be erased, thereby requiring a complicated control method.
In view of the above-described background, an object of the present invention is to provide a content addressable memory (CAM) that avoids the necessity for increasing the memory capacity and that simplifies control.
To achieve the above object, according to one aspect of the present invention, a content addressable memory of the present invention includes a memory region including a plurality of word memories, an address storage section for storing address data specifying a partial region of the memory region, and overwriting means for overwriting the contents of word memories in a region in the memory region excluding the partial region.
According to another aspect of the present invention, a content addressable memory includes a memory region including a plurality of word memories each including a predetermined plurality of bits, an address storage section for storing address data specifying a partial region of the memory region, and an overwriting means for performing retrieval by using predetermined data as retrieval data in response to a predetermined command and for overwriting the contents of word memories that contain storage data corresponding to the predetermined data used for the retrieval and that exist in a region in the memory region excluding the partial region.
According to still another aspect of the present invention, a content addressable memory is arranged such that storage data is stored in each of a plurality of word memories constituting a memory region so as to be overwritten, retrieval data is input, and storage data corresponding to the retrieval data that has been input is retrieved. The content addressable memory includes:
(1) an address storage section for storing address data specifying a partial region of the memory region; and
(2) an aging means for performing retrieval by using predetermined time stamp data in response to a predetermined aging command and erasing the contents of word memories that contain storage data corresponding to the time stamp data used for the retrieval and that exist in a region in the memory region excluding the partial region.
In the content addressable memory of the present embodiment, even when a server and the like have not been involved in communication for a long time, relevant address data which should not be erased is stored in the partial region. On the other hand, terminal-related data to be erased by the aging means is stored in the region excluding the partial region. Specifically, according to the present invention, address data to be stored in the address storage section is used to specify the partial region in which the specific data which should not be erased is stored. Thereby, in the present embodiment, different from the conventional content addressable memory, to control specific address data not to be erased, there is no need to provide a permanent bit in individual address data nor is there a need to perform read and write operations for address data in a MAC table every time retrieval is performed. Consequently, the necessity for increasing memory capacity can be avoided, and furthermore, control can be simplified.